0697. 数组的度【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法

1. 📝 题目描述

• leetcode

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

---

示例 1：

输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2，因为元素 1 和 2 的出现频数最大，均为 2。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2，所以返回 2。

示例 2：

输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6。

---

提示：

• nums.length 在 1 到 50,000 范围内。
• nums[i] 是一个在 0 到 49,999 范围内的整数。

2. 🎯 s.1 - 暴力解法

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var findShortestSubArray = function (nums) {
  // 使用 Map 记录每个元素的出现次数、首次出现位置和最后出现位置
  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      const item = map.get(nums[i])
      item.count++
      item.end = i
    } else {
      map.set(nums[i], {
        count: 1,
        start: i,
        end: i,
      })
    }
  }

  // 找到数组的度（最大出现次数）
  let maxCount = 0
  for (const item of map.values()) {
    maxCount = Math.max(maxCount, item.count)
  }

  // 找到具有最大出现次数的元素中最短的子数组长度
  let minLength = nums.length
  for (const item of map.values()) {
    if (item.count === maxCount) {
      minLength = Math.min(minLength, item.end - item.start + 1)
    }
  }

  return minLength
}

• 时间复杂度：$O(n)$
  • 需要遍历数组一次统计信息，再遍历 Map 两次
• 空间复杂度：$O(n)$
  • 最坏情况下每个元素都不同，Map 需要存储 n 个条目
• 暴力解法：
  • 核心思路：找出数组的度对应的数字 x，计算：$\mathrm{最}\mathrm{后}\mathrm{一}\mathrm{次}x\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{位}\mathrm{置}\mathrm{索}\mathrm{引}-\mathrm{第}\mathrm{一}\mathrm{次}x\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{位}\mathrm{置}\mathrm{索}\mathrm{引}+1$
  • 如果有多个数字满足度，则返回最小的计算结果